package leetcode;

public class Q0055 {

    /**
     * dp O(n^2) O(n)
     **/
//    public boolean canJump(int[] nums) {
//        boolean[] st = new boolean[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            if (i == 0 || st[i]) {
//                for (int j = 0; j <= nums[i]; j++) {
//                    if (i + j >= nums.length) break;
//                    st[i + j] = true;
//                }
//            }
//        }
//        return st[nums.length - 1];
//    }

    /**
     * 贪心 O(n) O(1)
     **/
    public boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i <= k; i++) {
            if (k >= nums.length - 1) {
                return true;
            }
            k = Math.max(k, i + nums[i]);
        }
        return false;
    }
}
